package com.xk._01基础篇._00LeetCode._树;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/*
 * 662_二叉树最大宽度：https://leetcode.cn/problems/maximum-width-of-binary-tree/
 */
public class Test04_二叉树最大深度 {
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null) return 0;

        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int maxWidth = 1;

        while(!queue.isEmpty()){
            int size = queue.size();
            int start = -1, end = -1;
            for(int i = 0; i < size; i++){
                TreeNode node = queue.pop();
                if(node != null){
                    queue.offer(node.left);
                    queue.offer(node.right);
                    if (start == -1){
                        start = i;
                    } else {
                        end = Math.max(i, end);
                    }
                    maxWidth = Math.max(maxWidth, end == -1 ? maxWidth : end - start + 1);
                } else {
                    queue.offer(null);
                    queue.offer(null);
                }
            }
            if (start == -1 && end == -1) break;
        }
        return maxWidth;
    }


    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(3);
        TreeNode n3 = new TreeNode(2);
        TreeNode n4 = new TreeNode(5);
        TreeNode n5 = new TreeNode(9);
        TreeNode n6 = new TreeNode(6);
        TreeNode n7 = new TreeNode(7);

        n1.right = n3;
        n3.left = n2;



        new Test04_二叉树最大深度().flatten(n1);
    }

    public void flatten(TreeNode root) {
        if(root == null) return;

        List<TreeNode> list = new LinkedList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node);
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }
        for(int i = 1; i < list.size(); i++){
            TreeNode cur = list.get(i), prev = list.get(i - 1);
            prev.left = null;
            prev.right = cur;
        }
    }
}
